package hot150;

// https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-interview-150
public class q13 {

    public int[] productExceptSelf(int[] nums) {
        return method1(nums, nums.length);
    }

    /**
     * 前缀和
     * 2 ms
     * 复杂度O(n)
     */
    public int[] method1(int[] nums, int n) {
        int[]left = new int[n + 1], right = new int[n + 1];
        left[0] = right[n] = 1;
        for (int i = 0 ; i < n ; i++) {
            // 前缀积
            left[i + 1] = left[i] * nums[i];
            // 后缀积
            right[n - 1 - i] = right[n - i] * nums[n - 1 - i];
        }
        int[]res = new int[n];
        for (int i = 0 ; i < n ; i++) {
            // 乘积 = 前缀积 * 后缀积
            res[i] = left[i] * right[i + 1];
        }
        return res;
    }
}
